//Given an array of intervals where intervals[i] = [starti, endi], merge all ove
//rlapping intervals, and return an array of the non-overlapping intervals that co
//ver all the intervals in the input. 
//
// 
// Example 1: 
//
// 
//Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
//Output: [[1,6],[8,10],[15,18]]
//Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
// 
//
// Example 2: 
//
// 
//Input: intervals = [[1,4],[4,5]]
//Output: [[1,5]]
//Explanation: Intervals [1,4] and [4,5] are considered overlapping.
// 
//
// 
// Constraints: 
//
// 
// 1 <= intervals.length <= 104 
// intervals[i].length == 2 
// 0 <= starti <= endi <= 104 
// 
// Related Topics 排序 数组 
// 👍 930 👎 0


package leetcode.editor.cn;

import java.util.*;

//Java：Merge Intervals
class P56MergeIntervals {
    public static void main(String[] args) {
        Solution solution = new P56MergeIntervals().new Solution();
        // TO TEST
        solution.merge(new int[][]{{1, 3}, {4, 5}, {1, 10}});

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[][] merge(int[][] intervals) {
            Arrays.sort(intervals, Comparator.comparingInt(o -> -o[1]));
            int count = intervals.length;
            for (int i = 0; i < intervals.length - 1; i++) {
                int[] intervalPre = intervals[i];
                int[] intervalNext = intervals[i+1];
                //可以合并
                if (intervalNext[1] >= intervalPre[0]) {
                    intervals[i + 1][0] = Math.min(intervalNext[0], intervalPre[0]);
                    intervals[i + 1][1] = intervalPre[1];
                    intervals[i] = null;
                    count--;
                }
            }
            int[][] res = new int[count][2];
            int index = 0;
            for (int i = 0; i < intervals.length; i++) {
                if (intervals[i] != null) {
                    res[index++] = intervals[i];
                }
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}